package com.zp.self.module.level_4_算法练习.算法.双指针.快慢指针;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author By ZengPeng
 */
public class 力扣_160_相交链表 {
    //测试
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        System.out.println(new 力扣_160_相交链表().getIntersectionNode(n1,null));
    }

    /**
     * 题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
     * 如果两个链表不存在相交节点，返回 null 。
     * 图示两个链表在节点 c1 开始相交：
     *
     * 题目数据 保证 整个链式结构中不存在环。
     * 注意，函数返回结果后，链表必须 保持其原始结构 。
     * 进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
     * 
     * 分析：
     *      1.使用set存储一个链表的所有节点，再变量另外一个链表，判断是否存在余set中
     *      #大神的优秀解法 ：两个指针同时移动，走完指向 另一条链表;
     *                      两个指针走的【节点长度】将会相同：lengthA+ lengthB
     *                      如果有相交的点
     *        循环条件： you ==null  && me ==null
     *        单步操作： if(you ==null ? headB : you) if(me ==null ? headA : me)
     *        终止条件： you == me
     *
     * 边界值注意：
     *      1.headA 、headB 都可能为null
     **/
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null) return null;
        Set<ListNode> set  = new HashSet<>();
        ListNode a = headA;
        ListNode b = headB;
        while(a!=null){
            set.add(a);
            a=a.next;
        }
        while(b!=null){
            if(set.contains(b)) return b;
            b=b.next;
        }
        return null;
    }


    /**
     *  循环条件： you ==null  && me ==null
     *  单步操作： if(you ==null ? headB : you) if(me ==null ? headA : me)
     *  终止条件： you == me
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA==null || headB==null) return null;
        ListNode you  = headA,me = headB;
        while (you !=null  ||  me !=null){
            if(you==me) return you;
            you = you ==null ? headB : you.next;
            me =  me ==null ? headA : me.next;
        }
        return null;
    }

}
